//二分图
class Solution {
public:
    vector<bool> vis;
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        int n = accounts.size();
        vis.resize(n,false);
        unordered_map<string,vector<int>> email_to_id;
        for(int i = 0;i < n;i++)
        {
            for(int j = 1;j < accounts[i].size();j++)
            {
                string cur = accounts[i][j];
                email_to_id[cur].push_back(i);
            }
        }

        unordered_set<string> s;
        auto dfs = [&](this auto&& dfs,int cur)->void
        {
            vis[cur] = true;
            for(int i = 1;i < accounts[cur].size();i++)
            {
                string email = accounts[cur][i];
                if(s.count(email)) continue;
                s.insert(email);

                for(auto& e : email_to_id[email])
                {
                    if(vis[e]) continue;
                    dfs(e);
                }
            }
        };

        vector<vector<string>> ans;
        for(int i = 0;i < n;i++)
        {
            if(vis[i]) continue;
            s.clear();

            dfs(i);

            vector<string> tmp({accounts[i][0]});
            tmp.insert(tmp.end(),s.begin(),s.end());
            sort(tmp.begin() + 1,tmp.end());
            ans.push_back(tmp);
        }

        return ans;
    }
};